package org.mmtk.plan.metrix;

import org.mmtk.plan.Plan;
import org.mmtk.plan.TraceLocal;
import org.mmtk.policy.Space;
import org.mmtk.utility.Log;
import org.mmtk.utility.deque.AddressDeque;
import org.mmtk.utility.deque.ObjectReferenceDeque;
import org.mmtk.vm.VM;
import org.vmmagic.pragma.Inline;
import org.vmmagic.pragma.Uninterruptible;
import org.vmmagic.unboxed.Address;
import org.vmmagic.unboxed.ObjectReference;

/**
 * This class implements the thread-local functionality for a transitive closure
 * over a mark-sweep space.
 */
@Uninterruptible
public final class MetrixTraceLocal extends TraceLocal {
	/****************************************************************************
	 * 
	 * Instance fields
	 */
	private ObjectReferenceDeque toEmpty;
	private ObjectReferenceDeque savedValues;
	private AddressDeque savedRootLocations;
	private DepthClosureCounts metricClosureCounts;
	private DepthClosureCounts checkClosureCounts;
	private ClosureCounts fixClosureCounts;
	private ClosureCounts closureCounts;
	private ClosureCounts currentClosureCounts;
	private RunCounts runCounts;
	private boolean initialTrace;
	
	/**
	 * Constructor
	 */	
	public MetrixTraceLocal(MetrixTrace pilotTrace) {
		super(Metrix.SCAN_MARK, pilotTrace);
		this.toEmpty = new ObjectReferenceDeque("toEmpty", pilotTrace.getToEmptyValuePool());
		this.savedRootLocations = new AddressDeque("savedRoots", pilotTrace.getSavedRootLocationPool());
		this.savedValues = new ObjectReferenceDeque("savedValues", pilotTrace.getSavedValuePool());
		this.metricClosureCounts = new DepthClosureCounts();
		this.checkClosureCounts = new DepthClosureCounts();
		this.fixClosureCounts = new ClosureCounts();
		this.closureCounts = new ClosureCounts();
		this.runCounts = new RunCounts();
	}

	/****************************************************************************
	 * 
	 * Externally visible Object processing and tracing, inherited from base
	 */
	/**
	 * Is the specified object live?
	 * 
	 * @param object
	 *            The object.
	 * @return True if the object is live.
	 */
	@Override
	@Inline
	public boolean isLive(ObjectReference object) {
		if (object.isNull())
			return false;
		if (Space.isInSpace(Metrix.MARK_SWEEP, object)) {
			return Metrix.myMsSpace.isLive(object);
		}
		return super.isLive(object);
	}

	/**
	 * This method is the core method during the trace of the object graph. The
	 * role of this method is to:
	 * 
	 * 1. Ensure the traced object is not collected. 2. If this is the first
	 * visit to the object enqueue it to be scanned. 3. Return the forwarded
	 * reference to the object.
	 * 
	 * In this instance, we refer objects in the mark-sweep space to the msSpace
	 * for tracing, and defer to the superclass for all others.
	 * 
	 * @param object
	 *            The object to be traced.
	 * @return The new reference to the same object instance.
	 */
	@Override
	@Inline
	public ObjectReference traceObject(ObjectReference object) {
		if (object.isNull()) return object;
		if (Space.isInSpace(Metrix.MARK_SWEEP, object))
			return Metrix.myMsSpace.traceObject(this, object);
		if (Space.isInSpace(Plan.VM_SPACE, object))
		    return (Plan.SCAN_BOOT_IMAGE) ? object : Plan.vmSpace.traceObject(this, object);
		if (Space.isInSpace(Plan.IMMORTAL, object))
		    return Plan.immortalSpace.traceObject(this, object);
		 if (Space.isInSpace(Plan.NON_MOVING, object))
		      return Plan.nonMovingSpace.traceObject(this, object);
		 if (Plan.USE_CODE_SPACE && Space.isInSpace(Plan.SMALL_CODE, object))
		      return Plan.smallCodeSpace.traceObject(this, object);
		if (Space.isInSpace(Plan.LOS, object) ||
				Plan.USE_CODE_SPACE && Space.isInSpace(Plan.LARGE_CODE, object)) {
			if(!this.initialTrace) {
				boolean live = isLive(object);
				if(!live) {
					logMessage("Non myms space object reached by a non initial scan should be live!!!");
					VM.objectModel.dumpObject(object);
				}
				ObjectReference narrowRef = VM.objectModel.getKathy(object);
				if(!(ObjectReference.fromObject(this.currentClosureCounts) == narrowRef)) {
					//have not put this object on stack during this closure
					/*logMessage("Setting LO narrow, space ");
					Space space = Space.getSpaceForObject(object);
					if (space == Metrix.myMsSpace) {
						Log.write(" Myms space ");	
					} else if (space == Plan.loSpace) {
						Log.write(" loSpace ");
					} else if (space == Plan.nonMovingSpace) {
						Log.write(" nonMovingSpace ");
					} else if (Plan.USE_CODE_SPACE && space == Plan.smallCodeSpace) {
						Log.write(" smallCodeSpace ");
					} else if (Plan.USE_CODE_SPACE && space == Plan.largeCodeSpace) {
						Log.write(" largeCodeSpace ");
					} else if (space == null) {
					     if (VM.VERIFY_ASSERTIONS) {
					       Log.write("space failure: "); Log.writeln(object);
					     }
					}
					Log.write(" narrow ");
					Log.writeln(narrowRef);
					Log.flush();
					*/
					VM.objectModel.setKathy(object, ObjectReference.fromObject(this.currentClosureCounts));
					//VM.objectModel.dumpObject(object);
					this.processNode(object);		
				}
			} else {
				//this is the first trace in a cycle, take care to remove narrow refs
				ObjectReference narrowRef = VM.objectModel.getKathy(object);
				if(ObjectReference.nullReference() != narrowRef) {
					//have not put this object on stack yet
					//Log.writeln("Cleaning narrow in other space object to track it in next closures");
					//Log.flush();
					//VM.objectModel.setNarrow(object, ObjectReference.nullReference());
				}
			}
			if (Space.isInSpace(Plan.LOS, object))
			      return Plan.loSpace.traceObject(this, object);
			    if (Plan.USE_CODE_SPACE && Space.isInSpace(Plan.LARGE_CODE, object))
			      return Plan.largeCodeSpace.traceObject(this, object);
		}
		    if (VM.VERIFY_ASSERTIONS) {
		      Space.printVMMap();
		      logMessage("Failing object => "); Log.writeln(object);
		      VM.assertions._assert(false, "No special case for space in traceObject");
		    }
		    return ObjectReference.nullReference();
	}

	/**
	 * Overriden to save the roots while processing
	 */
	@Inline
	public void processRoots(boolean save) {
		long savedRoots = 0;
		while (!rootLocations.isEmpty()) {
			Address entry = rootLocations.pop();
			if(save) {
				this.savedRootLocations.push(entry);
				savedRoots++;
			}
			processRootEdge(entry, true);
		}
		if(Metrix.PILOT_VERBOSE) {
			logMessage("Done processRoots, saved and processed roots number is ");
			Log.writeln(savedRoots);
			printClosureCounts("After processRoots ");
			Log.flush();
		}	
	}
	
	  /**
	   * Overriden to count my space objects pushed to the stack
	   * Add a gray object
	   *
	   * @param object The object to be enqueued
	   */
	  @Override
	  @Inline
	  public void processNode(ObjectReference object) {	  
		  if(!VM.objectModel.validRef(object)) {
	        this.currentClosureCounts.addIPushed();
	        printClosureCounts("processNode - object not valid, skiped ");
	        return;            
	      }
		  this.currentClosureCounts.addPushed();
		  if (Space.isInSpace(Metrix.MARK_SWEEP, object)) {
			  this.currentClosureCounts.addMsPushed();
		  }
		  super.processNode(object);
	  }

	
	/**
	 * Flush the local buffers of all dequeues.
	 */
	@Override
	public void flush() {
		super.flush();
		//this.savedRootLocations.flushLocal();
		//this.savedValues.flushLocal();
		this.toEmpty.flushLocal();
	}
	
	public void prepare() {
		super.prepare();
		this.initialTrace = true;
		this.closureCounts.init();
		this.metricClosureCounts.init();
		this.fixClosureCounts.init();
		if (Metrix.PILOT_VERBOSE) {
			//this.closureCounts.dumpObjectCounters("prepare closureCounts");
			//this.metricClosureCounts.dumpObjectCounters("prepare metricClosureCounts");
			//this.fixClosureCounts.dumpObjectCounters("prepare fixClosureCounts");
		}
	}

	public void release() {
		super.release();
		this.savedRootLocations.reset();
		this.savedValues.reset();
		this.toEmpty.reset();
		//TODO end cycle
		if (Metrix.PILOT_VERBOSE) {
			//this.closureCounts.dumpObjectCounters("release closureCounts");
			//this.metricClosureCounts.dumpObjectCounters("release metricClosureCounts");
			//this.fixClosureCounts.dumpObjectCounters("release fixClosureCounts");
		}
		this.runCounts.addCycle(this.metricClosureCounts, this.checkClosureCounts);
	}
	
	/**
	 * Finishing processing all GC work. This method iterates until all work
	 * queues are empty.
	 */
	@Inline
	public void completeTrace(boolean save, boolean cleanNarrow) {
		logMessage("completeTrace - enter\n");
		if (!rootLocations.isEmpty()) {
			logMessage("completeTrace - will process roots\n");
			processRoots(save);
		}

		assertMutatorRemsetsFlushed();
		logMessage("completeTrace - will process values\n");
		ObjectReference v;
		do {
			while (!values.isEmpty()) {
				v = values.pop();
				handlePopped(v, cleanNarrow);
			}
			processRememberedSets();
		} while (!values.isEmpty());
		assertMutatorRemsetsFlushed();
		logMessage("completeTrace - exit\n");
	}
	/************************************
	 * Methods to save and restore roots between closures
	 */
	private void restoreSavedRoots() {
		long numRestoredRoots = 0;
		while (!this.savedRootLocations.isEmpty()) {
			Address entry = this.savedRootLocations.pop();
			this.rootLocations.push(entry);
			numRestoredRoots++;
		}
		if (Metrix.PILOT_VERBOSE) {
			logMessage("Done restoreStoredRoots, numRestoredRoots=");
			Log.writeln(numRestoredRoots);
			Log.flush();
		}
	}
	
	private void restoreSavedValues() {
		long numRestoredValues = 0;
		while (!this.savedValues.isEmpty()) {
			ObjectReference v = this.savedValues.pop();
			if(isLive(v)) {
				this.processNode(v);
			} else {
				traceObject(v);
			}
			numRestoredValues++;
		}
		if (Metrix.PILOT_VERBOSE) {
			logMessage("Done restoreSavedValues, numRestoredValues=");
			Log.writeln(numRestoredValues);
			Log.flush();
		}
	}
	
	void savePreClosureState(boolean save) {
		markAndSaveValues(save);
		if (!rootLocations.isEmpty()) {
			processRoots(save);
		}
	}
	
	void restorePreClosureState() {
		restoreSavedRoots();
		restoreSavedValues();
	}
	
	//need to mark for we have cleaned the mark bits
	private void markAndSaveValues(boolean save) {
		long savedValues = 0;
		long restoredValues = 0;
		long invalid1 = 0;
		long invalid2 = 0;
		//all the values are popped and saved in 2 structures: 
		//temporarily in toEmpty and
		//till the next closure in savedValues
		while (!this.values.isEmpty()) {
			ObjectReference v = this.values.pop();
			if(!VM.objectModel.validRef(v)) {
				logMessage("markAndSaveValues - Popped object not valid, skipping");
	        	Log.flush(); 
	        	invalid1++;
	        	continue;            
	          }
			if(save) {
				this.savedValues.push(v);
				savedValues++;
			}
			this.toEmpty.push(v);		
		}
		//now values are restored from toEmpty
		while (!this.toEmpty.isEmpty()) {
			ObjectReference v = this.toEmpty.pop();
			if(!VM.objectModel.validRef(v)) {
				logMessage("markAndSaveValues - Popped from toEmpty object not valid, skipping");
	        	Log.flush(); 
	        	invalid2++;
	        	continue;            
	          }
			
			if(isLive(v)) {
				this.processNode(v);
			} else {
				traceObject(v);
			}
			restoredValues++;
		}
		if (Metrix.PILOT_VERBOSE) {
			logMessage("Done saveValues, savedValues=");
			Log.write(savedValues);
			Log.write(" restoredValues=");
			Log.write(restoredValues);
			Log.write(" invalid in values=");
			Log.write(invalid1);
			Log.write(" invalid in toEmpty=");
			Log.writeln(invalid2);
			printClosureCounts("After markAndSaveRoots ");
			Log.flush();
		}
	}
	
	void printClosureCounts(String message) {
		if (Metrix.PILOT_VERBOSE) {
			this.currentClosureCounts.dumpObjectCounters(message);
		}
	}
	
	void setRegularClosure() {
		this.initialTrace = false;
		this.currentClosureCounts = this.closureCounts;
	}
	
	void setMetricClosure() {
		this.initialTrace = true;
		this.currentClosureCounts = this.metricClosureCounts;
	}
	
	void setFixClosure() {
		this.initialTrace = false;
		this.currentClosureCounts = this.fixClosureCounts;
	}
	
	void setCheckClosure() {
		this.initialTrace = false;
		this.currentClosureCounts = this.checkClosureCounts;
	}
	
	void zeroClosureCounts() {
		this.currentClosureCounts.init();
	}
		
	/*************************************************************************
	 * Depth measuring trace
	 */
	/**
	 * Finishing processing all GC work. This method iterates until all work
	 * queues are empty.
	 */
	@Inline
	public void completeMetrixTrace(boolean save, boolean cleanNarrow) {
		logMessage("completeMetrixTrace - enter");
		if (!rootLocations.isEmpty()) {
			logMessage("completeMetrixTrace - rootLocations is not empty, calling processRoots");
			processRoots(save);
		} else {
			logMessage("completeMetrixTrace - rootLocations is empty!");
		}
		
		super.assertMutatorRemsetsFlushed();
		do {
			while (!values.isEmpty()) {
				copyValues();
				//printClosureCounts("completeMetrixTrace -  after copying values"); 	
				ObjectReference v;
				ObjectReference narrowRef;
				do {
					while (!toEmpty.isEmpty()) {
						v = toEmpty.pop();
						this.currentClosureCounts.addPopped(v);
						if (Space.isInSpace(Metrix.MARK_SWEEP, v)) {
							this.currentClosureCounts.addMsPopped();
							//Log.write("!KO! ");
							//Log.write(this.closureCounts.getMsPopped());
							//Log.write(" ");
							//Log.write(this.closureCounts.getMsPushed());
							//Log.write(" ");
							//flush();
							//objectModel.dumpObject(v);
							narrowRef = VM.objectModel.getKathy(v);
							if (ObjectReference.nullReference() != narrowRef) {
								if(cleanNarrow) {
									VM.objectModel.setKathy(v, ObjectReference.nullReference());
								} else {
									//Log.writeln("Tracing non null narrow reference");
									//Log.flush();
									this.currentClosureCounts.addNarrow();
									traceObject(narrowRef);
								}
							}
						}
						scanObject(v);
					}
					processRememberedSets();
				} while (!toEmpty.isEmpty());
				super.assertMutatorRemsetsFlushed();
				//printClosureCounts("completeMetrixTrace - after processing values");
			}
			processRememberedSets();
		} while (!values.isEmpty());
		super.assertMutatorRemsetsFlushed();

		this.currentClosureCounts.endClosure();
		logMessage("completeMetrixTrace - exiting,");
		Log.flush();
	}
	
	private void copyValues() {
		ObjectReference v;	
		long msObjects = 0;
		if(!this.toEmpty.isEmpty()) {
			logMessage("ERROR: toEmpty is NOT empty before copying");
		}
		while (!values.isEmpty()) {
			v = values.pop();
			if (Space.isInSpace(Metrix.MARK_SWEEP, v)) {
				msObjects++;
			}
			this.toEmpty.push(v);
		}
		
		this.currentClosureCounts.addDepth(msObjects);
		/*
		Log.write("Depth ");
		Log.write(this.closureCounts.getDepth());
		Log.write(" msObjects ");
		Log.write(msObjects);
		Log.write(" msPoppedObjects ");
		Log.writeln(this.closureCounts.getMsPopped());
		*/
	}	
	
	/******************************************
	 * Fix closure
	 */
	/*
	private long fixIncrement;
	@Inline
	public void completeFixTrace(boolean save) {
		//this.fixIncrement = this.metricClosureCounts.getFirstStallDepth();
		this.fixIncrement = 100;
		logMessage("completeFixTrace - enter, fixIncrement=");
		Log.writeln(fixIncrement);
		
	    if (!rootLocations.isEmpty()) {
	    	logMessage("completeFixTrace - roots not empty, processing roots");
	    	processRoots(save);
	    }
	    
	    assertMutatorRemsetsFlushed();
	    
	    ObjectReference v;
	    ObjectReference candidate = null;
	    int fromCandidate = 0;
	    long candidateLevel = 0;
	    boolean inMySpace;
	    do {
	      while (!values.isEmpty()) {
	        v = values.pop();
	        this.currentClosureCounts.addPopped(v);
	        inMySpace = Space.isInSpace(Metrix.MARK_SWEEP, v);
	        if(inMySpace) {
	        	long level = this.currentClosureCounts.getMsPushed() - this.currentClosureCounts.getMsPopped();
	        	long children = scanObjectPlus(v);
	        	//logMessage("completeFixTrace - popped ms space object, level= ");Log.write(level);
	        	//Log.write(", children=");Log.write(children);
	        	//Log.write(", candidate=");Log.write(candidate);
	        	//Log.write(", fromCandidate=");Log.write(fromCandidate);
	        	//Log.write(", candidateLevel=");Log.write(candidateLevel);
	        	//Log.writeln("");Log.flush();
	        	if(candidate == null) {
	        		if(children == 1) {
	        			ObjectReference narrowRef = VM.objectModel.getNarrow(v);
						if (ObjectReference.nullReference() != narrowRef) {
							//logMessage("!!! Candidate that already has Narrow ref, will not use");
						} else {
							//Log.writeln("Setting candidate");
							candidate = v;
							fromCandidate = 0;
							candidateLevel = level;
						}
	        		}
	        	} else {
	        		//we have candidate
	        		if(level < candidateLevel) {
	        			//out of the candidate's scope
	        			if(children == 1) {
		        			candidate = v;
		        			fromCandidate = 0;
		        			candidateLevel = level;
		        		} else {
		        			//Log.writeln("Abandoning candidate");
		        			candidate = null;
		        		}
	        		} else {
	        			fromCandidate++;
	        			if(fromCandidate >= fixIncrement) {
	        				//logMessage("Fixing and abandoning candidate");
	        				this.currentClosureCounts.addNarrow();
	        				VM.objectModel.setNarrow(candidate, v);
	        				//logMessage("From ");Log.flush();
	        				//VM.objectModel.dumpObject(candidate);
	        				//logMessage("To ");Log.flush();
	        				//VM.objectModel.dumpObject(v);
	        				candidate = null;
	        			}
	        		}
	        	}
	        } else {
	        	scanObject(v);
	        }
	      }
	      processRememberedSets();
	    } while (!values.isEmpty());
	    assertMutatorRemsetsFlushed();
	    
	    this.currentClosureCounts.endClosure();
	    Log.writeln("completeFixTrace - exit");
	    Log.flush();
	}
	*/
	public void completeFixTrace(TraceBranch ballancer, boolean save) {
		logMessage("completeFixTrace - enter\n");
		boolean stopBalance = false;
		ballancer.reset();
		
	    if (!rootLocations.isEmpty()) {
	    	logMessage("completeFixTrace - roots not empty, processing roots");
	    	processRoots(save);
	    }
	    
	    assertMutatorRemsetsFlushed();
	    
	    ObjectReference v;
	    boolean inMySpace;
	    long level;
	    int children;
	    do {
	      while (!values.isEmpty()) {
	        v = values.pop();
	        this.currentClosureCounts.addPopped(v);
	        inMySpace = Space.isInSpace(Metrix.MARK_SWEEP, v);
	        if(inMySpace) {
	        	this.currentClosureCounts.addMsPopped();
	        	level = this.currentClosureCounts.getMsPushed() - this.currentClosureCounts.getMsPopped();   	
	        	children = scanObjectPlus(v);  
	        	if(level < 300) {
	        		stopBalance = true;
	        	} if(!stopBalance) {
	        		ballancer.process(v, level, children);	
	        	}
	        } else {
	        	children = scanObjectPlus(v);
	        	if(children > 0) {
	        		Log.write("!!! Non ms object created ms children ");Log.writeln(children);
	        		Log.flush();
	        	}
	        }
	      }
	      processRememberedSets();
	    } while (!values.isEmpty());
	    assertMutatorRemsetsFlushed();
	    
	    this.currentClosureCounts.endClosure();
	    ballancer.report();
	    Log.writeln("completeFixTrace - exit");
	    Log.flush();
	}
	
	private int scanObjectPlus(ObjectReference v) {
		long pushedBefore = this.currentClosureCounts.getMsPushed();	
		scanObject(v);
		long pushedAfter = this.currentClosureCounts.getMsPushed();
		return (int)(pushedAfter - pushedBefore);
	}
	
	@Inline
	private void handlePopped(ObjectReference v, boolean cleanNarrow) {
	    ObjectReference narrowRef;
		if(!VM.objectModel.validRef(v)) {
        	logMessage("handlePopped - ERROR popped object not valid, skipping\n");
        	return;            
        }
        this.currentClosureCounts.addPopped(v);
        if (Space.isInSpace(Metrix.MARK_SWEEP, v)) {
        	this.currentClosureCounts.addMsPopped();
        	narrowRef = VM.objectModel.getKathy(v);
			if (ObjectReference.nullReference() != narrowRef) {
				if(cleanNarrow) {
					VM.objectModel.setKathy(v, ObjectReference.nullReference());
				} else {
					this.currentClosureCounts.addNarrow();
					traceObject(narrowRef);
				}
			}
        }	        
        scanObject(v);
	}
	
	@Inline
	protected void logMessage(String message) {
		if (Metrix.PILOT_VERBOSE) {
			Log.prependThreadId();
			Log.write(" - ");
			Log.write(message);
			Log.flush();
		}
	}
}
